In this section, we discuss a special family of graphs, which is
called expanders. Roughly speaking, in an expander graph, any
``small'' subset of vertices has a relatively ``large''
neighborhood. This concept originated from communication theory, and
has become more and more important in theoretical computer science.
You will be convinced after seeing the following concrete
definitions and applications of an expander.

\subsection{Cheeger's Constant}
Suppose we are given a graph $G=(V,E)$ and a subset $S\subseteq V$.
We define the border of a subgraph of $G$ as follows,
\begin{eqnarray*}
    \partial S=\{\{u,v\}|u\in S, v\not\in S\}
\end{eqnarray*}

Further, the following two quantities are of great importance to
define an expander graph.

\begin{definition}
    The \emph{Cheeger Ratio} for a vertex set $S$ is
    \begin{eqnarray*}
        h(S)={|\partial S|\over\min{\text{vol}(S),\text{vol}(\bar{S})}}
    \end{eqnarray*}
    where, $\bar{S}=V-S$
\end{definition}

\begin{definition}
    For any graph $G=(V,E)$, the \emph{Cheeger Constant} of $G$ is given by
    \begin{eqnarray*}
        h_G=\min_{S}h(S)
    \end{eqnarray*}
\end{definition}

\subsection{Cheeger's Inequality}
\begin{theorem}
    For any graph $G$,
    \begin{eqnarray}
        2h_G\ge \lambda_1\ge {h_G^2\over 2}\label{cheeger-ineq}
    \end{eqnarray}
\end{theorem}

\subsection{Expander Graph}
\begin{definition}
A family $\mathcal{G}=\{G_1, G_2,\dots\}$ of $d$-regular graphs is
an \emph{edge expander family} if there is a constant $c>0$ such
that $h(G)\ge c$ for each $G\in \mathcal{G}$.
\end{definition}
Notice that Cheeger's constant measures the number of neighbors that
a subset adjacent to. Requiring it to be greater than a positive
constant $c$ is the mathematical description of the requirement
mentioned above.

Typically, we want $d$ to be constant, though it is sometimes also
interesting to consider $d=\log{|G|}$ or even $d=|G|^{O(1)}$.

By the definition of an expander, $h_G$ has a positive lower bound
$c$, and by (\ref{cheeger-ineq}), one may notice that $\lambda_1\ge
{c^2\over 2}$, and thus $|1-\lambda_1|\le 1-{c^2\over 2}<1$ if $G$
is not a complete graph, meaning that a random walk on a
non-bipartite expander converges, and the better the expansion
property is, the faster the walk converges.

Some applications of expanders are listed in the next section.
